package myBitSet;

import java.util.Arrays;

/**
 * 模拟实现: 位图
 */
public class MyBitSet {
    public byte[] set = null;
    private int usedSize = 0; // 元素的总个数

    public MyBitSet() {
        this(1);
    }

    public MyBitSet(int size) {
        set = new byte[size + 1];
    }

    public int size() {
        return this.usedSize;
    }

    // 将某个 数 置为存在
    public void set(int val) {
        if (val < 0) {
            throw new ArrayIndexOutOfBoundsException(); // 数组越界异常
        }
        int setIdx = val / 8;
        if (setIdx > set.length) { // 越界了, 扩容
            set = Arrays.copyOf(set, (int) (1.5 * set.length));
        }
        int bitIdx = val % 8; // 在某一个比特位中的 下标

        set[setIdx] |= (1 << bitIdx);
        usedSize ++;
    }

    // 判断某个元素是否存在于 位图 中
    public  boolean get(int val) {
        int mapIdx = val / 8;
        int bitIdx = val % 8;
        if (mapIdx > set.length) {
            return false;
        }

        return (set[mapIdx] & (1 << bitIdx)) == 1;
    }

    // 将某个数置为不存在
    public void reset(int val) {
        int mapIdx = val / 8;
        int bitIdx = val % 8;
        if (mapIdx > set.length) {
            return ;
        }

        set[mapIdx] &= ~(1 << bitIdx);
    }
}
